import math
class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        return int((math.sqrt(5) / 5) * (math.pow((1 + math.sqrt(5)) / 2, n + 1) - math.pow((1 - math.sqrt(5)) / 2, n + 1)))
        
s = Solution()
print('ss', s.climbStairs(2))
print('ss', s.climbStairs(3))
print('ss', s.climbStairs(4))